graph = dict()
graph['start'] = {'a': 2, 'd': 5}
graph['a'] = {'b': 7, 'd': 8}
graph['b'] = {'final': 1}
graph['c'] = {'final': 1, 'b': 6}
graph['d'] = {'c': 4, 'b': 2}
graph['final'] = {}

costs = dict()
costs['a'] = 2
costs['b'] = float('inf')
costs['c'] = float('inf')
costs['d'] = 5
costs['final'] = float('inf')

parents = dict()
parents['a'] = 'start'
parents['b'] = None
parents['c'] = None
parents['d'] = 'start'
parents['final'] = None

used_list = []


def find_smallest_node(costs):
    smallest_node = None
    smallest_node_value = float('inf')
    for node_name in costs:
        if costs[node_name] < smallest_node_value and node_name not in used_list:
            smallest_node_value = costs[node_name]
            smallest_node = node_name
    return smallest_node


node = find_smallest_node(costs)
while node:
    for node_son in graph[node]:
        new_value = costs[node] + graph[node][node_son]
        if new_value < costs[node_son]:
            costs[node_son] = new_value
            parents[node_son] = node
    used_list.append(node)
    node = find_smallest_node(costs)

print('costs: ', costs, 'parents: ', parents)
